package com.xx.springboot.DataStructure.LeetCode.LinkedList;

import java.util.Stack;

/**
     请判断一个链表是否为回文链表。

     示例 1:

     输入: 1->2
     输出: false
     示例 2:

     输入: 1->2->2->1
     输出: true
     进阶：
     你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 */
public class isPalindrome {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
            return true;

        Stack<Integer> stack = new Stack<>();

        /**
         * 创建一个快指针 一个慢指针
         * 快指针的速度是慢指针的速度的两倍, 当快指针到达尾部时  慢指针正好走到链表的中间位置,  将前面一半的节点 压入栈中, 然后依次出栈 对比
         */
        ListNode l = head;
        ListNode r = head;

        while (head != null){
            if(r == null)
                break;
            if (r.next == null) {
                l = l.next;
                break ;
            }
            stack.push(l.val);
            l = l.next;
            r = r.next.next;
        }

        /**
         * 将 栈中的 元素依次出栈 进行对比
         */
        while (!stack.isEmpty()){
            if(stack.pop() != l.val)
                return false;

            l = l.next;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {1, 0, 1};

        ListNode listNode = new ListNode(arr);
        System.out.println(new isPalindrome().isPalindrome(listNode));

    }
}
